FFT & NTT

0. 符号约定

我们用大写字母表示多项式，小写字母表示多项式的系数，比如：

A (x) = a_{0} + a_{1} x + a_{2} x^{2} + \dots + a_{n} x^{n}

$ω_{n}^{k}$ 表示单位根，即

ω_{n}^{k} = \cos \frac{2 k π}{n} + i \sin \frac{2 k π}{n}

1. FFT

0. 基本思路

考虑对两个多项式进行乘法：

C (x) = A (x) B (x)

显然系数满足

c_{n} = \sum_{k = 0}^{n} a_{k} b_{n - k}

卷积

形如

c_{n} = \sum_{j \oplus k = n} a_{j} b_{k}

的式子叫作卷积。
对于多项式乘法，所计算的就是加法卷积。

朴素计算显然是 $Θ (n^{2})$ 的，很不优秀。这种不优秀实质上来源于系数表示，我们需要用其他的方法表示多项式。

注意到对于 $(n - 1)$ 次多项式，我们可以用 $n$ 个不同的点处的值来进行唯一表示。因此我们可以对多项式 $A$ 求出其点值 $A (x_{0}), A (x_{1}), \dots, A (x_{n - 1})$ ，对于多项式 $B$ 同理，求出 $B (x_{0}), B (x_{1}), \dots, B (x_{n - 1})$ 后，乘积 $C (x)$ 对应的点值显然有

C (x_{k}) = A (x_{k}) B (x_{k})

然后再进行插值即可得到 $C$ 的系数表示。

Caution

上面的 $n$ 为 $C$ 的次数 $+ 1$ 。

如此我们将 $Θ (n^{2})$ 的朴素卷积转化为了 $Θ (n)$ 的点值的乘法，关键在于求点值和插值两步的优化。

1. 求点值（DFT）

如果随意代入 $x_{k}$ ，复杂度仍为 $Θ (n^{2})$ ，没有优化。但是 $x_{i}$ 是可以任意选取的，我们可以选取更容易计算的点进行计算。这里的技巧是代入单位根 $x_{k} = ω_{n}^{k}$ 。

设 $A (x) = a_{0} + a_{1} x + \dots + a_{n - 1} x^{n - 1}$ （次数不够时高次项系数视为 $0$ 即可），有

A (x_{k}) = \sum_{j = 0}^{n - 1} a_{j} ω_{n}^{j k}

利用单位根 $ω_{n d}^{k d} = ω_{n}^{k}$ 的性质，我们能够轻易处理数列的拉伸操作，进而通过分治解决问题。

什么是拉伸操作？

考虑数列 $a_{0}, a_{1}, a_{2}, \dots$ ，拉伸变换将数列变为 $a_{0}, \underset{(k - 1) 个}{\underset{⏟}{0, \dots, 0}}, a_{1}, \underset{(k - 1) 个}{\underset{⏟}{0, \dots, 0}}, a_{2}, \dots$
在生成函数（以数列的每一项作为系数的幂级数）的语境下，
设 $A (x) = a_{0} + a_{1} x + a_{2} x^{2} + \dots$ ，拉伸后的序列对应的幂级数即为 $A (x^{k})$ 。

这里以二分治为例。方便起见将 $n$ 补为 $2$ 的幂。

奇偶分组便于使用拉伸操作：

设 $A_{0} (x) = a_{0} + a_{2} x + \dots + a_{n - 2} x^{n / 2 - 1}$ ， $A_{1} (x) = a_{1} + a_{3} x + \dots + a_{n - 1} x^{n / 2 - 1}$ ，则有

A (x) = A_{0} (x^{2}) + x A_{1} (x^{2})

代入单位根立得

A (ω_{n}^{k}) = A_{0} (ω_{n / 2}^{k}) + ω_{n}^{k} A_{1} (ω_{n / 2}^{k})

容易发现 $A_{0} (ω_{n / 2}^{k})$ 与 $A_{1} (ω_{n / 2}^{k})$ 即为两个子问题，因此可以分治求解……吗？

这里有一个问题，子问题中 $k$ 的取值仅为 $0, 1, \dots, n / 2 - 1$ ，还有另一半需要计算。

因此我们还需要代入 $ω_{n}^{k + n / 2} = - ω_{n}^{k}$ ，进行计算得

A (ω_{n}^{k + n / 2}) = A_{0} (ω_{n / 2}^{k}) - ω_{n}^{k} A_{1} (ω_{n / 2}^{k})

至此我们已经完成了快速计算点值的操作。由 Master 定理易知时间复杂度 $Θ (n \log n)$ 。

实质上 DFT 是一个序列变换的过程，它将 $a_{0}, \dots, a_{n - 1}$ 变换为了 $A (x_{0}), \dots, A (x_{n - 1})$ 。
并且这是一个线性的过程：

(\begin{matrix} 1 & 1 & 1 & \dots & 1 \\ 1 & ω_{n}^{1} & ω_{n}^{2} & \dots & ω_{n}^{n - 1} \\ 1 & ω_{n}^{2} & ω_{n}^{4} & \dots & ω_{n}^{2 (n - 1)} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & ω_{n}^{n - 1} & ω_{n}^{2 (n - 1)} & \dots & ω_{n}^{(n - 1) (n - 1)} \end{matrix}) (\begin{matrix} a_{0} \\ a_{1} \\ a_{2} \\ ⋮ \\ a_{n - 1} \end{matrix}) = (\begin{matrix} A (x_{0}) \\ A (x_{1}) \\ A (x_{2}) \\ ⋮ \\ A (x_{n - 1}) \end{matrix})

设 DFT 将序列 $X$ 变换为序列 $Y$ ，记作 $DFT (X) = Y$ ，根据线性性得到：

$DFT (X_{1} + X_{2}) = DFT (X_{1}) + DFT (X_{2})$
$DFT (k X) = k DFT (X)$

2. 插值（IDFT）

利用上面的观点，容易发现 IDFT 只需把上面矩阵的逆矩阵求出即可。而上面的矩阵是 Vandermonde 矩阵，逆矩阵熟知。

如果不会线代也可以直接启动拉格朗日插值：

A (x) = \sum_{k = 0}^{n - 1} A (x_{k}) \prod_{j \neq k} \frac{x - x_{j}}{x_{k} - x_{j}}

注意，利用单位根的性质，后面那个乘积项实际上是可以直接算出的，分子：

\prod_{j \neq k} (x - x_{j}) = \frac{x^{n} - 1}{x - ω_{n}^{k}}

分母：

\prod_{j \neq k} (x_{k} - x_{j}) = lim_{x \to x_{k}} \frac{x^{n} - 1}{x - ω_{n}^{k}} = n ω_{n}^{k (n - 1)} = n ω_{n}^{- k}

于是

\begin{aligned} \prod_{j \neq k} \frac{x - x_{j}}{x_{k} - x_{j}} & = \frac{ω_{n}^{k}}{n} \frac{x^{n} - 1}{x - ω_{n}^{k}} \\ = \frac{1}{n} (\frac{1}{1 - ω_{n}^{- k} x} - \frac{x^{n}}{1 - ω_{n}^{- k} x}) \\ = \frac{1}{n} (\sum_{j = 0}^{+ \infty} ω_{n}^{- j k} x^{j} - \sum_{j = 0}^{+ \infty} ω_{n}^{- j k} x^{j + n}) \\ = \frac{1}{n} (\sum_{j = 0}^{+ \infty} ω_{n}^{- j k} x^{j} - \sum_{j = 0}^{+ \infty} ω_{n}^{- (j + n) k} x^{j + n}) \\ = \frac{1}{n} \sum_{j = 0}^{n - 1} ω_{n}^{- j k} x^{j} \end{aligned}

代入整理得

\begin{aligned} A (x) & = \sum_{k = 0}^{n - 1} A (x_{k}) \frac{1}{n} \sum_{j = 0}^{n - 1} ω_{n}^{- j k} x^{j} \\ = \sum_{j = 0}^{n - 1} (\frac{1}{n} \sum_{k = 0}^{n - 1} A (x_{k}) ω_{n}^{- j k}) x^{j} \end{aligned}

于是（这里更换了下标以保证形式与 DFT 的统一）

a_{k} = \frac{1}{n} \sum_{j = 0}^{n - 1} A (x_{j}) ω_{n}^{- j k}

对比 DFT 的式子

A (x_{k}) = \sum_{j = 0}^{n - 1} a_{j} ω_{n}^{j k}

发现 IDFT 只不过是将单位根换成了 $ω_{n}^{- j}$ 并多了一个 $\frac{1}{n}$ 的系数。
在性质上我们实际上无法区分 $ω_{n}^{j}$ 和 $ω_{n}^{- j}$ ，算法与先前 DFT 完全一致。

上面关于 IDFT 的证明虽然直接但略显复杂，一个简单一些的证明可以看容斥与反演概论的最后一章。

3. 代码实现

To be finished